package com.bupt.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.bupt.datastruct.TreeNode;

public class TreeProblem {
	/**
	 * 前序遍历1，递归
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> preOrder(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		preHelper(root, res);
		return res;
	}

	/**
	 * 递归体
	 * 
	 * @param root
	 * @param res
	 */
	public void preHelper(TreeNode root, ArrayList<Integer> res) {
		if (root == null)
			return;
		res.add(root.val);
		preHelper(root.left, res);
		preHelper(root.right, res);
	}

	/**
	 * 前序遍历2，非递归，使用栈迭代
	 * 
	 * @param root
	 */
	public ArrayList<Integer> preOrderNonRecursive(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return null;
		Stack<TreeNode> s = new Stack<TreeNode>();
		while (root != null || !s.empty()) {
			// 向左走到头，栈中元素均已经遍历过
			if (root != null) {
				res.add(root.val);
				s.push(root);
				root = root.left;
			} else {
				// 向右走一步
				root = s.pop();
				root = root.right;
			}
		}
		return res;
	}

	/**
	 * 中序遍历1，递归
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> inOrder(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		inHelper(root, res);
		return res;
	}

	/**
	 * 递归体
	 * 
	 * @param root
	 * @param res
	 */
	public void inHelper(TreeNode root, ArrayList<Integer> res) {
		if (root == null)
			return;
		inHelper(root.left, res);
		res.add(root.val);
		inHelper(root.right, res);
	}

	/**
	 * 中序遍历2，非递归算法 同前序不一样的是出栈的时候才进行访问
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> inOrderNonRecursive(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Stack<TreeNode> s = new Stack<TreeNode>();
		// 向左走到头，
		while (root != null || !s.empty()) {
			if (root != null) {
				s.push(root);
				root = root.left;
			} else {
				// 向右走一步
				root = s.pop();
				res.add(root.val);
				root = root.right;
			}
		}
		return res;
	}

	/**
	 * 后序遍历1，递归
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> postOrder(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		inHelper(root, res);
		return res;
	}

	/**
	 * 递归体
	 * 
	 * @param root
	 * @param res
	 */
	public void postHelper(TreeNode root, ArrayList<Integer> res) {
		if (root == null)
			return;
		inHelper(root.left, res);
		inHelper(root.right, res);
		res.add(root.val);
	}

	/**
	 * 后序遍历2，非递归算法1 比较复杂，设定pre指针和cur指针，表示前一个和现在访问的节点，分情况讨论
	 * cur的左右子树都为空，说明是叶子节点，直接出栈访问
	 * （1）如果pre的左孩子或者右孩子是cur，那么说明遍历在往下走，按访问顺序继续，即如果有左孩子
	 * ，则是左孩子进栈，否则如果有右孩子，则是右孩子进栈，如果左右孩子都没有，则说明该结点是叶子，可以直接访问并把结点出栈了。
	 * （2）如果反过来，cur的左孩子是pre
	 * ，则说明已经在回溯往上走了，但是我们知道后序遍历要左右孩子走完才可以访问自己，所以这里如果有右孩子还需要把右孩子进栈
	 * ，否则说明已经到自己了，可以访问并且出栈了。 （3）如果cur的右孩子是pre，那么说明左右孩子都访问结束了，可以轮到自己了，访问并且出栈即可。
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> postOrderNonRecursive1(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode pre = null;
		s.push(root);
		while (!s.isEmpty()) {
			TreeNode cur = s.peek();
			// pre的左孩子或者右孩子是cur，那么说明遍历在往下走，按访问顺序继续
			if (pre == null || pre.left == cur || pre.right == cur) {
				// cur有左孩子
				if (cur.left != null) {
					s.push(cur.left);
					// cur有右孩子
				} else if (cur.right != null) {
					s.push(cur.right);
					// cur是叶子节点
				} else {
					res.add(cur.val);
					s.pop();
				}
				// cur的左孩子是pre,如果有右孩子还需要把右孩子进栈
			} else if (cur.left == pre && cur.right != null) {
				s.push(cur.right);
				// cur左孩子是pre,cur无右孩子或cur的右孩子是pre
			} else {
				res.add(cur.val);
				s.pop();
			}
			pre = cur;
		}
		return res;
	}

	/**
	 * 二叉树后序遍历非递归算法 1）如果当前栈顶元素的右结点存在并且还没访问过（也就是右结点不等于上一个访问结点），那么就把当前结点移到右结点继续循环；
	 * 2）如果栈顶元素右结点是空或者已经访问过，那么说明栈顶元素的左右子树都访问完毕，应该访问自己继续回溯了。
	 * 
	 * @param root
	 * @return
	 */
	public ArrayList<Integer> postOrderNonRecursive2(TreeNode root) {
		ArrayList<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode pre = null;
		while (root != null || !s.empty()) {
			if (root != null) {
				s.push(root);
				root = root.left;
			} else {
				TreeNode peek = s.peek();
				if (peek.right != null && peek.right != pre) {
					root = peek.right;
				} else {
					res.add(peek.val);
					pre = peek;
					s.pop();
				}
			}
		}
		return res;
	}

	/**
	 * 树高度非递归解法,使用队列可解
	 * 
	 * @return
	 */
	public int treeHeight(TreeNode root) {
		if (root == null)
			return 0;
		TreeNode tail = root;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.add(root);
		int height = 0;
		while (!q.isEmpty()) {
			TreeNode t;
			TreeNode tempTail = null;
			do {
				t = q.remove();
				if (t.left != null) {
					q.add(t.left);
					tempTail = t.left;
				}
				if (t.right != null) {
					q.add(t.right);
					tempTail = t.right;
				}
			} while (t != tail);
			height++;
			tail = tempTail;
		}
		return height;
	}

	/**
	 * 树按层次遍历,
	 * 
	 * @param root
	 * @return
	 */
	public List<List<Integer>> levelOrderII(TreeNode root) {
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		if (root == null)
			return res;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.add(root);
		while (!q.isEmpty()) {
			List<Integer> levelList = new ArrayList<Integer>();
			int levleWidth = q.size();
			for (int k = 1; k <= levleWidth; k++) {
				TreeNode t = q.remove();
				levelList.add(t.val);
				if (t.left != null)
					q.add(t.left);
				if (t.right != null)
					q.add(t.right);
			}
			res.add(levelList);
		}
		List<List<Integer>> reverse = new ArrayList<List<Integer>>();
		for (int i = 0; i < res.size(); i++) {
			reverse.add(res.get(res.size() - 1 - i));
		}
		return reverse;
	}

	/**
	 * url : https://leetcode.com/problems/binary-tree-right-side-view/
	 * 求树每一层的最右一个节点； 使用一个队列即可，和分层遍历思想一样
	 * 
	 * @param root
	 * @return
	 */
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if (root == null)
			return res;
		Queue<TreeNode> q = new LinkedList<TreeNode>();
		q.add(root);
		while (!q.isEmpty()) {
			int levelSize = q.size();
			for (int k = 1; k <= levelSize; k++) {
				TreeNode t = q.remove();
				if (t.left != null)
					q.add(t.left);
				if (t.right != null)
					q.add(t.right);
				if (k == levelSize)
					res.add(t.val);
			}
		}
		return res;
	}
	/**
	 * 判断一个数是否是二叉查找树
	 * @param root
	 * @return
	 */
	public boolean isValidBST(TreeNode root) {
		if(root == null) return true;
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode t = root;
		int pre = Integer.MIN_VALUE;
		boolean flag = true;
		while(!s.isEmpty() || t!=null){
			if(t != null){
				s.push(t);
				t = t.left;
			}else {
				t = s.pop();
				if(flag || t.val > pre){
					pre = t.val;
					flag = false;
				}else {
					return false;
				}
				t = t.right;
			}
		}
		return true;
	}
}
